package com.cwj.algorithm.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @author chenwujie
 * @date 2020/11/1010:42
 */
public class MergeSort {
    public static <T extends Comparable<? super T>> void sort(List<T> data){
        sort(data, 0, data.size() - 1);
    }
    public static <T extends Comparable<? super T>> void sort(List<T> data, int i, int j){
        if(j - i == 0){
            return;
        }
        if(j - i == 1){
            if(greater(data.get(i), data.get(j))){
                exchange(data, i, j);
            }
            return;
        }
        int k = (i + j)/2;
        sort(data, i, k);
        sort(data, k + 1, j);
        merge(data, i , k, j);
    }

    public static <T extends Comparable<? super T>> void sort(T[] data){
        sort(data, 0, data.length - 1);
    }

    public static <T extends Comparable<? super T>> void sort(T[] data, int i, int j){
        if(j - i == 0){
            return;
        }
        if(j - i == 1){
            if(greater(data[i], data[j])){
                exchange(data, i, j);
            }
            return;
        }
        int k = (i + j)/2;
        sort(data, i, k);
        sort(data, k + 1, j);
        merge(data, i, k, j);
    }

    private static <T extends Comparable<? super T>> void merge(List<T> data, int i, int k, int j){
        List<T> assistList = new ArrayList<T>();
        int left = i;
        int right = k + 1;
        int l = 0;
        while(left <= k && right <= j){
            if(greater(data.get(left), data.get(right))){
                assistList.add(l++, data.get(right++));
            }else{
                assistList.add(l++, data.get(left++));
            }
        }
        while (left <= k){
            assistList.add(l++, data.get(left++));
        }
        while (right <= j){
            assistList.add(l++, data.get(right++));
        }
        for (T t : assistList) {
            data.set(i++, t);
        }
    }

    private static <T extends Comparable<? super T>> void merge(T[] data, int i, int k, int j){
        Object[] assist = new Object[j - i + 1];

        int left = i;
        int right = k + 1;
        int l = 0;
        while(left <= k && right <= j){
            if(greater(data[left], data[right])){
                assist[l++] = data[right++];
            }else{
                assist[l++] = data[left++];
            }
        }
        while (left <= k){
            assist[l++] = data[left++];
        }
        while (right <= j){
            assist[l++] = data[right++];
        }
        for (Object o : assist) {
            // TODO: 类型检查警告，待完善
            data[i++] = (T) o;
        }
//        System.arraycopy(assist, 0, data, i, assist.length);
    }

    private static <T extends Comparable<? super T>> boolean greater(T a, T b){
        return a.compareTo(b) > 0;
    }

    private static <T extends Comparable<? super T>> void exchange(List<T> data, int i, int j){
        T temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    private static <T extends Comparable<? super T>> void exchange(T[] data, int i, int j){
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
